\documentclass[10pt,a4paper]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage{float}
\usepackage{subfig}

\author{Benito Vitale, Dardo Marasca}
\title{Object Oriented Virtual Memory}


\begin{document}
\maketitle

\begin{abstract}
En este trabajo se analizan los problemas y posibles soluciones a la hora de implementar memoria virtual en SqueakNOS. Se toman en cuenta varias aproximaciones con sus ventajas y desventajas. Al final elegiremos e implementaremos una de estas, tratando de quedarnos del lado más puro de objetos. 
\end{abstract}

\newpage

\section*{Motivación}
En la actualidad el auge de la programación orientada a objetos es indiscutible, la mayor parte de los proyectos tienden a ser desarrollados bajo este paradigma. 

Sin dudas uno de los mayores referentes, sino el mayor, de este suceso es Smalltalk. Quien se imaginaria que aquel pequeño sistema creado por Alan Kay a fines de la década de los 80, seria el responsable de una de las mayores revoluciones en la industria del software.

En la actualidad existen cientos de lenguajes orientados a objetos, aunque la gran mayoría son híbridos y mezclan conceptos de varios paradigmas.  A pesar de todo esto Smalltalk se sigue manteniendo como el referente indiscutible del paradigma, a pesar de su acotado uso en la industria (en comparación de otros lenguajes que están de moda). Una de las principales diferencias que tiene Smalltalk con el resto, es la existencia un mundo vivo de objetos. 

Cuando trabajamos en un entorno de objetos Smalltalk no estamos interactuando con un editor de textos, sino con un entorno objetos que nacen, crecen y mueren. Esta idea bastante radical crea un ambiente de trabajo muy ameno y natural, en donde simplemente jugamos a ser un \"Dios\" en este pequeño mundo, creando objetos y dándoles responsabilidades con el fin de simular algún dominio que de la realidad que nos interese. 

Por otro lado, en la gran mayoría de los otros lenguajes orientados a objetos el desarrollo es mucho mas estático. Interactuamos solamente con un editor de textos y cada vez que queremos ver nuestro sistema funcionando tenemos que volver al clásico compilar-ejecutar heredado de los lenguajes estructurados. 

A pesar de esta utopía del pequeño mundo smalltalk, no podemos escapar de las limitaciones a nivel arquitectura que lamentablemente existen. Una de las mas importantes, y la cual vamos a intentar atacar en este trabajo, es que el tamaño del mundo es limitado, es decir, la cantidad de objetos que podemos tener existiendo en la imagen al mismo tiempo es limitada. Esto provoca que nos veamos obligados a tener que almacenar objetos en diferentes medios externos al mundo, por ejemplo, serializando los objetos a archivos en disco. Debido a esta limitación nuestra utopía de un mundo de objetos se ve levemente distorsionada, en este articulo intentamos buscar algunas soluciones a este problema.


\section*{SqueakNOS}

SqueakNOS es una modificación al código de la maquina virtual de Squeak (actualmente basado en Pharo) que permite que podamos correr una imagen de smalltalk sin depender un sistema operativo. 

Además tiene reificados en objetos dentro del entorno Smalltalk gran parte de los dispositivos que componen nuestra PC, de tal manera que la mayoría de los servicios que normalmente provee un sistema operativo puedan ser implementados como objetos en Smalltalk. De esta forma servicios tales como el acceso a disco, administración de memoria, sistema de archivos y acceso a dispositivos están programados dentro de la imagen. 

SqueakNOS no esta exento de las limitaciones de arquitecturas mencionadas anteriormente, con lo cual nuestro mundo es nuevamente limitado. En particular, dado que SqueakNOS actualmente carece de un servicio que permite virtualizar la memoria RAM, el tamaño de la imagen está limitado por la cantidad memoria RAM disponible.

\section*{Objetivo}

La idea de este trabajo es relajar un poco la limitación sufre SqueakNOS sobre el tamaño del mundo. El objetivo es implementar el sistema de virtualización de memoria del cual carece. Si bien esto no nos exenta de seguir limitados por la arquitectura, nos permitiría tener un mundo que no este acotado por la cantidad de memoria física disponible (la cual frecuentemente suele ser poca en comparación con la capacidad de almacenamiento).

Sin embargo la limitación aun se mantiene, dado que en la implementación actual de las maquinas virtuales cada objeto es referenciado directamente por un puntero a su posición en memoria. De esta forma estamos limitados por la cantidad de memoria que puede ser direccionada según la arquitectura. Por ejemplo, corriendo sobre una arquitectura de 32 bits nuestra imagen no puede ser mayor a 4gb.

\section*{Virtual Memory}

Virtual Memory es una técnica de administración de memoria utilizada por los sistemas operativos modernos. La idea es evitar que los procesos de accedan directamente a la memoria física. En lugar su lugar utilizan un espacio de memoria virtual, sin desconocer a que parte de la memoria física están accediendo realmente. Para lograr esto, el sistema operativo (normalmente con ayuda del hardware) debe interceptar todos los accesos a memoria y traducir cada dirección virtual a su respectiva dirección física. Como cada proceso usa un espacio de direccionamiento virtual diferente, permite que puedan correr al mismo tiempo y no existan conflictos si es que varios procesos utilizan la misma dirección de memoria. 

Dado que mantener un registro de las relaciones entre direcciones de memoria directamente seria muy costoso, normalmente se divide a la memoria en bloques y la relación entre dirección virtual y física se realiza a este nivel. Los sistemas modernos dividen el espacio de memoria en bloques consecutivos que no se solapan y mantienen tablas para asociar la ubicación virtual de estos bloques con su respectiva dirección en la memoria física. 

El sistema mas utilizado es Paginación, cuya idea es dividir la memoria en bloques de tamaño fijo llamados paginas. Cuando un proceso requiere una dirección que se encuentra en una determinada pagina, el sistema busca en una serie de tablas para obtener su ubicación en memoria física. Este sistema no esta limitado a la memoria RAM para almacenar sus paginas, comúnmente se utiliza algún dispositivo adicional de mayor tamaño para almacenar algunas paginas, así de esta forma no estamos limitados por el tamaño de la memoria RAM. Algunos sistemas utilizan archivos en disco para este propósito, mientras que otros utilizan particiones en disco especiales, las cuales están optimizadas para trabajar con esta funcionalidad. Esto nos permite que un proceso pueda acceder a cualquier parte de la memoria virtual y pueda utilizar tanta como la arquitectura permita direccionar. 

\begin{figure}[h]
  \begin{center}
    \includegraphics[width=250pt]{./img/virtualMemory.png}
    \caption{Ejemplo de sistema de paginación}
  \end{center}
\end{figure}

Dado que el acceso a memoria es mucho mas rápido que el acceso a disco, un sistema de paginación que utiliza una disco para almacenar paginas, debe preocurar que las paginas accedidas siempre este en memoria. Para lograr esto el sistema va intercambiando paginas entre memoria y el disco, intentando siempre que las paginas más usadas estén en memoria. Cuando una pagina no se encuentra en memoria, el sistema busca la pagina en disco y la carga en memoria en algún frame libre de la memoria. 

Una de las estrategias criticas a tener en cuenta este tipo de sistema es la política de desalojo de paginas. Esta técnica define que pagina hay que desalojar cuando tenemos ocupados todos los frames de la memoria. Una buena estrategia siempre intenta minimizar la necesidad de ir a disco a buscar paginas faltantes.

Algunas de las políticas mas simples son:

\begin{itemize}
  \item Random.
  \item Fifo.
  \item Not recently used (NRU).
  \item Least recently used (LRU).
\end{itemize}


No vamos a explicar cada una de estas estrategias en el informe dado que escapa del alcance del mismo. Solo es importante entender utilizar una u otra estrategia implica un \"tradeoff\" entre minimizar la necesidad de acceder a disco y minimizar el overhead creado al aplicar una estrategia en particular. 

Algunas técnicas necesitan que el hardware provea determinada funcionalidad y solo pueden ser implementadas en este hardware. Porque de otra, forma el overhead de simular esta funcionalidad por software seria demasiado alto. 

Con respecto a la traducción entre direcciones virtuales y físicas, la implementación mas común se basa en utilizar una jerarquía de tablas, las cuales son indexadas por un conjunto de bits de la dirección virtual. 

Por ejemplo: en un sistema de paginación para una arquitectura de 32 bits con paginas de 4k (4096 bytes), se utiliza un directorio de paginas donde cada entrada apunta a una tabla de pagina, la cual contiene la dirección física. Para indexar dentro de esta estructura se utilizan los 10 bits más significativos como índice para el directorio de paginas, los siguientes 10 para indexar la tabla de paginas y los últimos 12 corresponden al offset dentro de la misma. Además cada entrada contiene bits que pueden ser utilizados para controlar acceso, marcar las paginas como solo lectura, verificar si fue accedida, si fue escrita, etc. Algunos de estos bits, como el bit de accedida, son actualizados directamente por el hardware.

\begin{figure}[h]
  \begin{center}
    \includegraphics[width=250pt]{./img/directorio.png}
    \caption{Paginación con direcciones de 32 bits}
  \end{center}
\end{figure}

\section*{Bootstrapping}
Cuando nos referimos a Bootstrapping estamos hablando del proceso de arranque del sistema, el cual no puede ser ignorado en nuestro trabajo. 

Actualmente el proceso de arranque de SqueakNOS es relativamente simple dado que utiliza el gestor de arranque GRUB. SqueakNOS se releva a el bootloader gran parte de la implementación del inicio del sistema.

GRUB se encarga de:

\begin{itemize}
  \item Pasar a modo protegido.
  \item Inicializar el modo de vídeo.
  \item Cargar la VM a memoria.
  \item Cargar la imagen a memoria.
\end{itemize}

Por lo tanto, SqueakNOS arranca con todo lo necesario ya cargado en memoria. 

El problema que encontramos para implementar memoria virtual, es que la imagen podría no llegar a entrar en memoria, por lo tanto la actual implementación de bootstrapping no nos sirve demasiado (GRUB no podría cargar la imagen dado que no entra en memoria). 

Si bien no llegamos a implementar esta parte del sistema estudiamos las siguientes soluciones:

\begin{description}
  \item[Cargar en 2 etapas:] La idea de esta implementación es utilizar una imagen pequeña que se encargue de ir cargando la imagen principal. La ventaja de esta solución radica en que no habría que modificar el bootstrapping actual, pero sin embargo necesitamos implementar la funcionalidad necesaria de pasar el control entre las imágenes.
  \item[Cargar desde la Virtual Machine:] Esta solución implicaría modificar la Virtual Machine para que sea ella misma la que se encargue de levantar lo que necesite de la imagen. El problema de esta implementación es que necesitamos leer la imagen desde el disco (cosa que antes GRUB nos resolvía), lo que implica programar los drivers de disco y el sistema de archivos.
\end{description}

En todas las soluciones la idea general es cargar lo mínimo necesario de la imagen y que el resto vaya siendo cargado a memoria a medida que suceden los fallos de páginas.

\section*{Garbage Collector}

 El Garbage Collector (GC de ahora en más) es el encargado de liberar la memoria utilizada por objetos que no pueden ser referenciados desde ningún otro. Esta funcionalidad es necesaria dado que sino existiera tendríamos la imagen llena de objetos perdidos, y como consecuencia, nos quedaríamos sin memoria disponible. 
 
La idea general del GC es recorrer la imagen buscando aquellos objetos que no son referenciados desde ningún otro, para luego eliminarlos de la memoria. El GC normalmente se activa cada cierto intervalo de tiempo o cuando ocurre algún determinado evento, por ejemplo, cuando nos estamos quedando sin memoria disponible.
 
Hay estudiadas muchas estrategias para realizar esta tarea, algunas implementaciones de GC mas conocidas son:

\begin{itemize}
  \item Mark and Sweep GC.
  \item Generational GC.
  \item Reference Counting.
\end{itemize}
 
 
El GC se encuentra implementado en la VM y durante su ejecución el entorno de Smalltalk queda pausado. Este ultimo detalle es el principal problema que encontramos a la hora de implementar memoria virtual, dado que esto significa que mientras el GC esta ejecutándose no puede correr código smalltalk, por lo tanto, nuestro sistema de paginación no podría funcionar durante este periodo de tiempo. 

Entonces si el GC intenta acceder a una parte de la imagen que no esta en memoria nos encontraríamos en un problema: como nuestro sistema de paginación esta escrito en Smalltalk, no podríamos responder al fallo de pagina.

A continuación enumeraremos las posibles soluciones que encontramos para este problema.
 
\subsection*{Soluciones}
\subsubsection*{Paginación en la VM}
La solución inmediata seria implementar el sistema de paginación en la Virtual Machine. De esta forma a pesar que se genere un fallo de pagina durante la ejecución del GC, podríamos atajarlo y resolverlo sin problemas. 

El principal problema que presenta esta funcionalidad es que al estar fuera del entorno de Smalltalk, no podemos usar la implementación existente para acceder al archivo de paginación. Esto implicaría que necesitamos implementar toda esta funcionalidad a bajo nivel, lo cual escapa de los fines del trabajo.

\subsubsection*{Ignorar paginas en disco}
Esta implementación radica en modificar el GC para que este ignore aquellos objetos que se encuentran en paginas que no están en memoria. La ventaja de esta estrategia es que evitaríamos que el GC se levanten paginas del disco. Y dado que el GC tiene que recorrer toda la imagen,  con esta implementación podríamos muy buena performance.

La mayor dificultad que tiene esta solución se encuentra en decidir que pasa con las referencias que tienen los objetos que están en disco, dado que si las ignoramos podríamos llegar a eliminar objetos de forma accidental. 

Estudiamos las siguientes soluciones a este problema:

\begin{itemize}
  \item Al momento de bajar una pagina a disco, recorreríamos los objetos que están siendo referenciados por los objetos que viven en esta pagina y los marcaríamos como "no borrables". Entonces durante el GC no deberíamos eliminar los objetos con esta marca. De igual forma al momento de subir la pagina a memoria debería desmarcar todos estos objetos.
  \item Cuando bajo una pagina a disco, recorro todo el grafo de referencias de los objetos que están en las paginas que estoy bajando y almaceno todas estas referencias en un objeto "dummy". Dicho objeto debera vivir en una zona de memoria que no puede bajarse a disco. De esta forma mantengo las referencias, entonces me aseguro que el GC no va a eliminar objetos de forma accidental. Como la solución anterior, cuando vuelvo a subir la pagina tengo que eliminar estas referencias del objeto "dummy".
\end{itemize} 

La mayor diferencias entre las soluciones radica en que en la primera necesitaría modificar el comportamiento de GC, mientras que en la segunda no.

\subsubsection*{Imagen kernel}

Dado que durante el GC no puedo ejecutar código Smalltalk en la imagen, una posible solución seria tener dos imágenes cargadas en memoria: una pequeña que implementa el sistema de paginación y una segunda que representa mi imagen principal, como se muestra en la figura \ref{fig:memdist}. 

\begin{figure}[h]
  \begin{center}
    \includegraphics[width=250pt]{./img/memdist.png}
    \caption{Distribución de la memoria virtual}
    \label{fig:memdist}
  \end{center}
\end{figure}


Entonces cuando sea necesario hacer un GC sobre la imagen principal, se pasa el control a la imagen mas pequeña y esta se encargará de \"limpiar\" la imagen principal.

Para poder llevar a cabo esta implementación necesitamos lo siguiente:

\begin{itemize}
  \item La imagen kernel debe ser lo suficientemente reducida para no generar ningún fallo de pagina.
  \item Implementar un GC en Smalltalk que sea capaz de correr sobre una imagen alocada en una posición de memoria especifica. 
  \item Poder lanzar el GC de la imagen kernel según algún criterio, esto implicaría la capacidad de pasar el control entre las imágenes (por ej: usando una primitiva).
  \item Un sistema de paginación capaz de administrar la zona de memoria física donde se encuentra la imagen principal usando memoria virtual.
\end{itemize}

De esta manera cuando estemos realizando el GC a la imagen principal desde la imagen kernel, dado que nuestro GC esta en Smalltalk, aun podríamos seguir utilizando nuestro sistema de paginación reificado  y por lo tanto responder a los fallos de paginas que sean provocados.

\section*{Implementación Actual}
\subsection*{Decisiones de implementación}
Optamos por el modelo con dos imágenes. De esta forma, la imagen kernel va a estar completamente cargada en memoria (lo cual nos evita tener que modificar el bootstraping) y va a poder realizar la paginación y GC de la otra imagen.

Para simplificar las cosas, vamos a trabajar con un solo directorio de páginas. También vamos a implementar varias estrategias de desalojo.

\subsection*{Modelo de clases}


\begin{figure}[H]
 \centering

  \subfloat[VirtualMemoryManager]{\label{fig:p}\includegraphics[width=0.4\textwidth]{../clases/VirtualMemoryManager.png}}              l 
%\hspace{0.2\textwidth} 
\hfill
  \subfloat[VirtualPageFaultHandler]{\label{fig:pf}\includegraphics[width=0.4\textwidth]{../clases/VirtualPageFaultHandler.png}}

\end{figure}


\begin{figure}[H]
  \begin{center}
    \includegraphics[width=0.9\textwidth]{../clases/PageContainer.png}
    \caption{PageContainer}
    \label{fig:pc}
  \end{center}
\end{figure}

\begin{figure}[H]
  \begin{center}
    \includegraphics[width=0.9\textwidth]{../clases/PageFrameManager.png}
    \caption{PageFrameManager}
    \label{fig:pfm}
  \end{center}
\end{figure}

\begin{figure}[H]
 \centering
%\hfill  
  \subfloat[Pagel]{\label{fig:p}\includegraphics[width=0.1\textwidth]{../clases/Page.png}}              
%\hfill 
\hspace{0.2\textwidth} 
  \subfloat[PageFrame]{\label{fig:pf}\includegraphics[width=0.5\textwidth]{../clases/PageFrame.png}}
%\hfill  
%  \subfloat[A mouse]{\label{fig:mouse}\includegraphics[width=0.3\textwidth]{mouse}}
%\caption{Pictures of animals}
%  \label{fig:animals}

\end{figure}


\subsection*{Ventajas y desventajas}

\begin{itemize}

  \item Implementación más simple que las otras (más objetos y menos código)
  \item No requiere hacer cambios de contexto (a nivel procesador)
  \item Al tener un solo directorio, este es compartido con la imagen kernel y disminuye la capacidad de direccionamiento.

\end{itemize}

\subsection*{Ejemplo de Page Fault}

\begin{figure}[H]
  \begin{center}
    \includegraphics[width=1.1\textwidth]{../pageFault.png}
    \caption{Atención de PageFault sin desalojo}
    \label{fig:pfault}
  \end{center}
\end{figure}


En la implementación actual el PageFault (de ahora en más PF) llega al PageManager que se lo pasa a \verb+PageFaultHandler>>handlePageFaultOn:+

Con Virtual Memory, el PageManager tiene un handler particular para el área de memoria de la imagen grande.
Este handler es VirtualPageFaultHandler quien conoce al VirtualMemoryManager y le solicita que cargue la página faltante (loadPageFor:)

El primer paso es checkear si hay frames líbres en el contenedor. Si no los hay, si envia el mensaje swapOffAny para bajar a disco cualquier página. Acá entra la pollítica de desalojo (\verb+PageFrameManager>>candidateToUnload+) para decidir cual de todas. Una vez elegida se hace el swapOff de la misma, moviendola del contenedor de memoria a de disco.

Una vez obtenido el frame libre, se hace el swapOn de la página faltante copiando el contenido del disco a la memoria.


\newpage
\section*{Conclusión}

Al intentar implementar el sistema de paginación virtual nos encontramos con el conflicto de atacar el mismo dominio de problema desde dos niveles completamente diferentes. Por un lado tenemos al GC que corre al nivel de VM y por otro lado a nuestro sistema de paginación escrito en smalltalk que vive dentro del mundo de Smalltalk. Sumado el hecho de que cuando corre el GC no puede correr nada del entorno Smalltalk y que es puede generar fallos de paginas, no es posible  implementar un sistema de paginación solamente modelándolo dentro de la imagen. Cualquier camino que tomemos implicaba en cierto punto tener que movernos de dominio y trabajar sobre la implementación de la Virtal Machine. 

Por otro lado, si obviamos los problemas ligados a la arquitectura de la VM, modelar el sistema de paginación usando objetos fue bastante simple y natural. Pudimos, por ejemplo, dotar al sistema de la capacidad de cambiar sus estrategias de paginación simplemente cambiando un objeto, aprovechando de que reificamos las estrategias de desalojo bajo una jerarquía polimórfica. Si bien el modelo que planteamos tiene muchas cosas para criticar, intentamos que respete lo mejor posible el espíritu del paradigma.

Uno de los puntos mas interesantes es que teniendo la implementación completa de un sistema paginación en Smalltalk, nos permitiría implementar de forma bastante simple un sistema de memoria transaccional.  


\newpage
\section*{Bibliografía}
\begin{itemize}

  \item Smalltalk-80. Adele Goldberg and David Robson.
  \item Pharo by Example. Andrew P. Black, Stéphane Ducasse, Oscar Nierstrasz and Damien Pollet.
  \item A Tour of the Squeak Object Engine. Tim Rowledge.
  \item Smalltalk-80: Bits of History, Word of Advice. Glenn Krasner.
  \item http://squeaknos.blogspot.com/.
  \item Modern Operating Systems. Andrew S. Tanenbaum.

\end{itemize}

\end{document}
